﻿#include <iostream>
using namespace std;
#include <map>
#include <vector>
#include <string>



// *******位运算************************************************************
//************************************************************
//************************************************************


//乐扣：338.比特位计数
// https://leetcode.cn/problems/counting-bits/
class Solution
{
public:
    vector<int> countBits(int n)
    {
        vector<int> ans(n + 1);
        int x = 0;
        while (x <= n)
        {
            int count = 0;
            for (int i = 0; i < 32; i++)
            {
                if (x & (1 << i))
                {
                    count++;
                }

            }
            ans[x] = count;
            x++;
        }

        return ans;
    }
};


//乐扣：191.位1的个数
// https://leetcode.cn/problems/number-of-1-bits/
class Solution
{
public:
    int hammingWeight(int n)
    {
        int count = 0;
        for (int i = 0; i < 32; i++)
        {
            if (n & (1 << i))
            {
                count++;
            }
        }
        return count;

    }
};


//461.汉明距离
// https://leetcode.cn/problems/hamming-distance/
class Solution
{
public:
    int hammingDistance(int x, int y)
    {
        int count = 0;
        for (int i = 0; i < 32; i++)
        {
            if (((x >> i) & 1) != ((y >> i) & 1))
            {
                count++;
            }
        }
        return count;

    }
};

//136.只出现一次的数字
// https://leetcode.cn/problems/single-number/ 
class Solution
{
public:
    int singleNumber(vector<int>& nums)
    {
        int ret = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            ret ^= nums[i];
        }
        return ret;
    }
};

// 260.只出现一次的数字Ⅲ
// https://leetcode.cn/problems/single-number-iii/ 
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int x = 0;
        for (int num : nums)
        {
            x ^= num;
        }
        // 防止溢出
        int l = (x == INT_MIN ? x : x & (-x));
        int num1 = 0, num2 = 0;
        for (int num : nums)
        {
            if (num & l)
            {
                num1 ^= num;
            }
            else
            {
                num2 ^= num;
            }
        }
        return { num1, num2 };
    }
};


//判断字符是否唯一
// https://leetcode.cn/problems/is-unique-lcci/
class Solution
{
public:
    bool isUnique(string astr)
    {
        if (astr.size() > 26)
        {
            return false;
        }

        int bitMap = 0;
        for (auto e : astr)
        {
            int i = e - 'a';
            if (((bitMap >> i) & 1) == 1)
            {
                return false;
            }
            bitMap |= 1 << i;
        }
        return true;
    }
};

// 丢失的数字
// https://leetcode.cn/problems/missing-number/
class Solution
{
public:
    int missingNumber(vector<int>& nums)
    {
        int x = 0;
        for (auto e : nums)
        {
            x ^= e;
        }
        for (int i = 0; i <= nums.size(); i++)
        {
            x ^= i;
        }
        return x;

    }
};


// 两整数之和
// https://leetcode.cn/problems/sum-of-two-integers/
class Solution
{
public:
    int getSum(int a, int b)
    {

        while (b)
        {
            int tmp = a & b;
            a ^= b;
            b = (tmp << 1);
        }
        return a;

    }
};


// 只出现一次的数字Ⅱ
// https://leetcode.cn/problems/single-number-ii/
class Solution
{
public:
    int singleNumber(vector<int>& nums)
    {
        int ret = 0;
        for (int i = 0; i < 32; i++)
        {
            int sum = 0;
            for (auto e : nums)
            {
                if (((e >> i) & 1) == 1)
                {
                    sum++;
                }
            }
            sum %= 3;
            if (sum)
            {
                ret |= (sum << i);
            }
        }
        return ret;
    }
};


// 消失的两个数字
// https://leetcode.cn/problems/missing-two-lcci/
class Solution
{
public:
    vector<int> missingTwo(vector<int>& nums)
    {
        int x = 0, a = 0, b = 0;
        for (auto e : nums)
        {
            x ^= e;
        }
        for (int i = 1; i <= nums.size() + 2; i++)
        {
            x ^= i;
        }

        int flag = 0;
        while (1)
        {
            if ((x >> flag) & 1)
            {
                break;
            }
            else
            {
                flag++;
            }

        }
        for (auto e : nums)
        {
            if (((e >> flag) & 1) == 1)
            {
                b ^= e;
            }
            else
            {
                a ^= e;
            }
        }
        for (int i = 1; i <= nums.size() + 2; i++)
        {
            if (((i >> flag) & 1) == 1)
            {
                b ^= i;
            }
            else
            {
                a ^= i;
            }
        }
        return { a, b };


    }
};


// 替换所有的问号
//  https://leetcode.cn/problems/replace-all-s-to-avoid-consecutive-repeating-characters/
class Solution
{
public:
    string modifyString(string s)
    {
        int n = s.size();
        for (int i = 0; i < n; i++)
        {
            if (s[i] == '?')
            {
                for (char ch = 'a'; ch <= 'z'; ch++)
                {
                    if ((i == 0 || ch != s[i - 1]) && (i == n - 1 || ch != s[i + 1]))
                    {
                        s[i] = ch;
                        break;
                    }

                }
            }
        }
        return s;
    }
};

// 提莫攻击
// https://leetcode.cn/problems/teemo-attacking/
class Solution
{
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration)
    {
        int sum = 0, x = 0, n = timeSeries.size();
        for (int i = 1; i < n; i++)
        {
            x = timeSeries[i] - timeSeries[i - 1];
            if (x >= duration)
            {
                sum += duration;
            }
            else
            {
                sum += x;
            }
        }
        return sum + duration;

    }
};



class Solution
{
public:
    string convert(string s, int numRows)
    {
        // 处理边界情况
        if (numRows == 1) return s;

        string ret;
        int d = 2 * numRows - 2, n = s.size();

        // 1. 先处理第⼀⾏
        for (int i = 0; i < n; i += d)
            ret += s[i];

        // 2. 处理中间⾏
        for (int k = 1; k < numRows - 1; k++) // 枚举每⼀⾏
        {
            for (int i = k, j = d - k; i < n || j < n; i += d, j += d)
            {
                if (i < n) ret += s[i];
                if (j < n) ret += s[j];
            }
        }

        // 3. 处理最后⼀⾏
        for (int i = numRows - 1; i < n; i += d)
            ret += s[i];
        return ret;
    }
};



//外观数列
// https://leetcode.cn/problems/count-and-say/
class Solution
{
public:
    string countAndSay(int n)
    {
        string s = "1";
        for (int i = 1; i < n; i++)
        {
            string tmp;
            int len = s.size();
            int left = 0, right = 0;
            int count = 0;
            while (right < len)
            {
                while (s[left] == s[right] && right < len)
                {
                    right++;
                }
                tmp += (right - left + '0');
                tmp += s[left];
                left = right;
            }
            s = tmp;

        }
        return s;

    }
};



// 数青蛙
// https://leetcode.cn/problems/minimum-number-of-frogs-croaking/
class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        int C = 0, R = 0, O = 0, A = 0, K = 0, cnt = 0;
        for (auto& c : croakOfFrogs) {
            if (c == 'c') {
                if (K)   K--;
                else    cnt++;
                C++;
            }
            else if (c == 'r') {
                C--;
                R++;
            }
            else if (c == 'o') {
                R--;
                O++;
            }
            else if (c == 'a') {
                O--;
                A++;
            }
            else {
                A--;
                K++;
            }
            if (C < 0 || R < 0 || O < 0 || A < 0)    return -1;
        }
        if (C || R || O || A)    return -1;
        return cnt;
    }
};


// 颜色分类
// https://leetcode.cn/problems/sort-colors/
class Solution
{
public:
    void sortColors(vector<int>& nums)
    {
        int left = -1, right = nums.size();
        int cur = 0;
        while (cur < right)
        {
            if (nums[cur] == 0)
            {
                swap(nums[++left], nums[cur++]);
            }
            else if (nums[cur] == 2)
            {
                swap(nums[--right], nums[cur]);
            }
            else
            {
                cur++;
            }
        }


    }
};


// 排序数组
//  https://leetcode.cn/problems/sort-an-array/
class Solution
{
public:
    int getRandom(vector<int>& nums, int left, int right)
    {
        int r = rand();
        return nums[r % (right - left + 1) + left];
    }

    void qsort(vector<int>& nums, int begin, int end)
    {
        if (begin >= end)
        {
            return;
        }
        // 数组分三块
        int key = getRandom(nums, begin, end);
        int i = begin, left = begin - 1, right = end + 1;
        while (i < right)
        {
            if (nums[i] < key)
            {
                swap(nums[++left], nums[i++]);
            }
            else if (nums[i] == key)
            {
                i++;
            }
            else swap(nums[--right], nums[i]);
        }
        qsort(nums, begin, left);
        qsort(nums, right, end);
    }

    vector<int> sortArray(vector<int>& nums)
    {
        qsort(nums, 0, nums.size() - 1);
        return nums;
    }


};



// 数组中第K个最大元素
// https://leetcode.cn/problems/kth-largest-element-in-an-array/
class Solution
{
public:
    int getRandom(vector<int>& nums, int left, int right)
    {
        return nums[rand() % (right - left + 1) + left];
    }
    int qsort(vector<int>& nums, int begin, int end, int k)
    {
        if (begin == end) return nums[begin];
        int key = getRandom(nums, begin, end);
        int left = begin - 1, right = end + 1, i = begin;
        while (i < right)
        {
            if (nums[i] < key)
            {
                swap(nums[++left], nums[i++]);
            }
            else if (nums[i] == key)
            {
                i++;
            }
            else
            {
                swap(nums[--right], nums[i]);
            }
        }

        int c = end - right + 1, b = right - left - 1;
        if (c >= k)
        {
            return qsort(nums, right, end, k);
        }
        else if (b + c >= k)
        {
            return key;
        }
        else
        {
            return qsort(nums, begin, left, k - b - c);
        }
    }
    int findKthLargest(vector<int>& nums, int k)
    {
        srand(time(NULL));
        return qsort(nums, 0, nums.size() - 1, k);
    }
};


// 仓库管理Ⅲ
// https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/
class Solution
{
public:
    int getRandom(vector<int>& nums, int begin, int end)
    {
        return nums[rand() % (end - begin + 1) + begin];
    }
    void qsort(vector<int>& nums, int begin, int end, int k)
    {
        if (begin >= end)
        {
            return;
        }
        int key = getRandom(nums, begin, end);
        int left = begin - 1, right = end + 1, i = begin;
        while (i < right)
        {
            if (nums[i] < key)
            {
                swap(nums[++left], nums[i++]);
            }
            else if (nums[i] == key)
            {
                i++;
            }
            else
            {
                swap(nums[--right], nums[i]);
            }
        }
        int a = left - begin + 1, b = right - left - 1;
        if (a > k)
        {
            qsort(nums, begin, left, k);
        }
        else if (a + b >= k)
        {
            return;
        }
        else
        {
            qsort(nums, right, end, k - a - b);
        }


    }
    vector<int> inventoryManagement(vector<int>& stock, int cnt)
    {
        srand(time(NULL));
        qsort(stock, 0, stock.size() - 1, cnt);
        return { stock.begin(), stock.begin() + cnt };


    }
};


// 排序数组
// https://leetcode.cn/problems/sort-an-array/
class Solution
{
    vector<int> tmp;

public:
    void mergeSort(vector<int>& nums, int left, int right)
    {
        if (left >= right) return;
        int mid = (left + right) >> 1;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right)
        {
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        }
        ;
        // 处理没有遍历完的数组
        while (cur1 <= mid)
        {
            tmp[i++] = nums[cur1++];
        }
        while (cur2 <= right)
        {
            tmp[i++] = nums[cur2++];
        }

        for (int i = left; i <= right; i++)
        {
            nums[i] = tmp[i - left];
        }

    }


    vector<int> sortArray(vector<int>& nums)
    {
        tmp.resize(nums.size());
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }


};


// 招式拆解
// https://leetcode.cn/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/
class Solution {
public:
    int dismantlingAction(string arr) 
    {
        unordered_map<char, int> dic;
        int i = -1, res = 0, len = arr.size();
        for (int j = 0; j < len; j++) {
            if (dic.find(arr[j]) != dic.end())
                i = max(i, dic.find(arr[j])->second); // 更新左指针
            dic[arr[j]] = j; // 哈希表记录
            res = max(res, j - i); // 更新结果
        }
        return res;
    }
};


// 找到第k位数字
// https://leetcode.cn/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/
class Solution {
public:
    int findKthNumber(int k) {
        int digit = 1;
        long start = 1;
        long count = 9;
        while (k > count) { // 1.
            k -= count;
            start *= 10;
            digit += 1;
            count = digit * start * 9;
        }
        long num = start + (k - 1) / digit; // 2.
        return to_string(num)[(k - 1) % digit] - '0'; // 3.
    }
};



// 两数相加
// https://leetcode.cn/problems/add-two-numbers/
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
    {
        ListNode* cur1 = l1, * cur2 = l2;
        ListNode* newhead = new ListNode(0); // 创建⼀个虚拟头结点，记录最终结果
        ListNode* prev = newhead; // 尾指针
        int flag = 0;
        while (cur1 || cur2 || flag)
        {
            if (cur1)
            {
                flag += cur1->val;
                cur1 = cur1->next;
            }
            if (cur2)
            {
                flag += cur2->val;
                cur2 = cur2->next;
            }
            prev->next = new ListNode(flag % 10);
            prev = prev->next;
            flag /= 10;
        }
        prev = newhead->next;
        delete newhead;

        return prev;
    }
};


// 两两交换链表中的结点
// https://leetcode.cn/problems/swap-nodes-in-pairs/
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* newHead = head->next;
        head->next = swapPairs(newHead->next);
        newHead->next = head;
        return newHead;
    }
};


// 重排链表
// https://leetcode.cn/problems/reorder-list/
class Solution
{
public:
    ListNode * swapPairs(ListNode * head)
    {
        if (head == nullptr || head->next == nullptr) return head;
        ListNode* newHead = new ListNode(0);
        newHead->next = head;
        ListNode* prev = newHead,* cur = prev->next,* next = cur->next,* nnext= next->next;
        while (cur && next)
        {
             // 交换结点
            prev->next = next;
            next->next = cur;
            cur->next = nnext;
             // 修改指针
            prev = cur; // 注意顺序
            cur = nnext;
            if (cur) next = cur->next;
            if (next) nnext = next->next;
        }
        cur = newHead->next;
        delete newHead;
        return cur;
    }
};


// 合并k个升序链表
// https://leetcode.cn/problems/merge-k-sorted-lists/
class Solution
{
    struct cmp
    {
        bool operator()(const ListNode* l1, const ListNode* l2)
        {
            return l1->val > l2->val;
        }
    };
public:
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
        for (auto l : lists)
        {
            if (l)
            {
                heap.push(l);
            }
        }
        ListNode* newnode = new ListNode(0);
        ListNode* prev = newnode;
        while (!heap.empty())
        {
            ListNode* t = heap.top();
            heap.pop();
            prev->next = t;
            prev = t;
            if (t->next)
            {
                heap.push(t->next);
            }
        }
        prev = newnode->next;
        delete newnode;
        return prev;

    }
};


// k个一组翻转链表
// https://leetcode.cn/problems/reverse-nodes-in-k-group/
class Solution
{
public:
    ListNode* reverseKGroup(ListNode* head, int k)
    {
        int n = 0;
        ListNode* cur = head;
        while (cur)
        {
            cur = cur->next;
            n++;
        }
        n /= k;
        ListNode* newhead = new ListNode(0);
        ListNode* prev = newhead;
        cur = head;

        for (int i = 0; i < n; i++)
        {
            ListNode* tmp = cur;
            for (int j = 0; j < k; j++)
            {
                ListNode* next = cur->next;
                cur->next = prev->next;
                prev->next = cur;
                cur = next;
            }
            prev = tmp;
        }
        prev->next = cur;
        cur = newhead->next;
        delete newhead;
        return cur;


    }
};
